package NewCoder;

import java.util.HashMap;
import java.util.LinkedHashSet;

public class BM101 {
    public int[] LFU (int[][] operators, int k) {
        // write code here
        LFUCache lfu=new LFUCache(k);
        int len=0;
        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==2){
                len++;
            }
        }
        int[] res=new int[len];
        len=0;
        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==1){
                lfu.set(operators[i][1],operators[i][2]);
            }else{
                res[len++]=lfu.get(operators[i][1]);
            }
        }
        return res;
    }

    class LFUCache {
        int cap;//记录LFU缓存最大容量
        int minFreq;//记录最小频次
        HashMap<Integer,Integer> KeyToVal=new HashMap<>();
        HashMap<Integer,Integer> KeyToFreq=new HashMap<>();
        HashMap<Integer, LinkedHashSet<Integer>> FreqToKey=new HashMap<>();
        public LFUCache(int capacity) {
            this.cap=capacity;
            this.minFreq=0;
        }

        public int get(int key) {
            if(!KeyToVal.containsKey(key)){
                return -1;
            }
            increaseFreq(key);
            return KeyToVal.get(key);
        }

        public void set(int key, int value) {
            if(this.cap<=0) return;
            if(KeyToVal.containsKey(key)){
                KeyToVal.put(key,value);
                increaseFreq(key);
                return;
            }
            if(KeyToVal.size()>=cap){
                removeMinFreqKey();
            }
            KeyToVal.put(key,value);
            KeyToFreq.put(key,1);
            FreqToKey.putIfAbsent(1,new LinkedHashSet<>());
            FreqToKey.get(1).add(key);
            this.minFreq=1;//插入新key后，最小的freq一定是1

        }
        private void removeMinFreqKey(){
            //freq最小的key列表
            LinkedHashSet<Integer> keyList=FreqToKey.get(this.minFreq);
            //其中最先别插入的那个就是应该被淘汰的key
            int deletekey=keyList.iterator().next();
            keyList.remove(deletekey);
            if(keyList.isEmpty()){
                FreqToKey.remove(this.minFreq);
            }
            KeyToVal.remove(deletekey);
            KeyToFreq.remove(deletekey);

        }


        private void increaseFreq(int key){
            int freq=KeyToFreq.get(key);
            KeyToFreq.put(key,freq+1);
            FreqToKey.get(freq).remove(key);
            FreqToKey.putIfAbsent(freq+1,new LinkedHashSet<>());
            FreqToKey.get(freq+1).add(key);
            if(FreqToKey.get(freq).isEmpty()){
                FreqToKey.remove(freq);
                if(freq==this.minFreq){
                    this.minFreq++;
                }
            }
        }
    }
}
